package com.demo.datastructure.reorder.quickSort;

import com.demo.datastructure.reorder.Example;

/**
 * @author ljr
 * @version 1.0
 * @description: 三向切分
 * @date 2021/10/1 12:39
 */
public class SimlpeQuickSort3 implements Example {

    @Override
    public void sort(Comparable[] a, int low, int high) {
        if(high <= low) return;
        int lt = low, i = low+1, gt = high;
        Comparable v = a[low];
        while(i <= gt){
            int cmp = a[i].compareTo(v);
            if(cmp < 0) exch(a, lt++, i++);
            else if(cmp > 0) exch(a, i, gt--);
            else i++;
        }
        sort(a,low,lt-1);
        sort(a,gt+1,high);
    }
}
